The present invention is in the field of routing digital data over a data-packet-network (DPN) and pertains more particularly to methods and apparatus for classifying packets to determine routing requirements.
In the art of routing digital data through data-packet networks, research and development of methods for more efficient handling of data packets continues. Generally speaking, a data packet is a digitized and organized block of binary data that is a xe2x80x9cpackagedxe2x80x9d portion of a specific communication or data transfer from a source location to an ultimate destination on a network. A data packet typically has one or more headers, and a data body. The packet headers are used for data routing through the network. During routing from a source location to a routed destination, data packets may be processed at one or more stops or routing points along the way. These hops, as they are often termed, are between data routers and, in some cases, server nodes distributed through the network. Data packets are, for example, commonly routed over the Internet network and commonly include Internet Protocol (IP) headers and Transmission Control Protocol (TCP) headers. It is well-known in the routing art that there are typically several hops for a packet between a source and a destination. It is also well-known that there are industry-accepted and applied procedures and protocols in routing, so that the many parts of the Internet (for example) will continue to operate seamlessly, even though hardware and software from many different sources and companies is used. Further, the procedures by which routers function involve many internal processes and messages between routers. For example, to operate successfully every router needs to keep track of its own position in the overall network, the position and functioning characteristics of its nearest neighbors, the output (egress) ports by which it must transmit packets previously received at input (ingress) ports to be sure the packets follow a best route to the final destination, and so on.
A router typically has more than one ingress port and more than one egress port. The ports are often organized so each specific port functions for both ingress and egress. For descriptive purposes, however, it is quite useful to treat ingress and egress ports as separate entities, because they are logically separate and are often implemented as separate entities. A packet received at any ingress port is pre-processed at that port by, for example, checking the header information for type, source and destination, port numbers, and so forth, and determining which of potentially many rules and processes apply, and then processing the packet by applying the determined procedures. Some packets may be data packets for such as a video stream or a Web page, for example, which may be processed by re-transmitting them at whatever egress port is determined to be coupled to the next node to which they should go on the way to the final destination. Other packets may be determined to be queries from a neighboring router, which may be diverted to a CPU for a subsequent answer to be prepared and sent back to the neighbor. There are many possibilities, and every packet must be processed so a determination can be made, and the correct action taken.
One of the functions in the art that routers practice on packets has to do with a quick decision to pass a packet on to further processing, or to simply drop the packet. This function in the state-of-the-art takes place at both ingress and egress ports. There are a variety of reasons that an incoming packet received at an ingress port might be dropped. For example, packets of an unknown type, which may be michevious, should not be processed. As another simple example, packets that have a destination that cannot be reached according to current routing tables can be dropped, because they cannot go anywhere anyway. There are a number of other possibilities well-known in the art.
There are also a variety of reasons why packets at an egress port might need to be dropped, even though they have been accepted and processed in the router, and have arrived at an egress port. There may be, for example, requests from certain organizations for receiving only packets meeting certain criteria. There are a number of other reasons for dropping packets at output ports well-known in the art. In many cases the reasons for pass and drop are port specific.
A typical way that pass/drop determination is made at either ingress or egress is by matching certain fields from a packet with fields in an Access Control List (ACL). The ACL is simply a lookup mechanism for matching the fields and returning a bit determined by the match (or mismatch) to pass (further process or transmit) or drop the packet. The implementation of such ACLs is described further in this specification in the section entitled xe2x80x9cDescription of the Preferred Embodimentsxe2x80x9d below.
Because the reasons for dropping at ingress or at egress ports may differ, it makes good sense in the art to implement ingress pass/drop determinations separately from egress pass/drop determinations. Still, doing the determination to pass or drop requires the mechanisms to accomplish the function. That is, to do an ACL lookup and return a bit every ingress port and egress port must have the hardware and/or software to do so. Typically hardware implementation is preferred for speed.
Because of the additional complexity, latency and expense of doing pass/drop determination at both ingress and egress, some manufacturers may prefer to implement the ACL pass/drop function at only ingress ports, and to forego implementing the function at egress. Until the present invention this would mean not having the function at all at the egress ports.
What is clearly needed is a method and apparatus that enables a router or server to accomplish both ingress and egress pass/drop functionality at ingress ports, obviating the need for the mechanisms to accomplish the function at egress ports.
In a preferred embodiment of the invention, in a network packet router having one or more ingress and egress ports, a system implemented at an ingress port for egress pass/drop determination for packets is provided, comprising a rule set comprising header combinations and values for which a pass/drop decision may be applied, the set including an egress port identity for each header combination and value set, and a mechanism noting pertinent headers of a specific incoming packet, and an egress port to which the packet is to be sent, comparing the headers with rules in the rule set, and returning a determination of a rule to be applied.
In some embodiments of the invention the rule set association takes the form of a lookup table, and the rule returned may determine the pass or drop for the packet. Certain preferred embodiments are capable of implementation in the Internet.
In some cases there is a second lookup table for accomplishing ingress rule determinations without egress port numbers. Also in some embodiments there is a content addressable memory (CAM) used for header combination matches, and pass/drop is determined by the address location of any match. In some embodiments of the system there are two sections in the CAM, and pass or drop is determined by the section of the CAM wherein a content match is found. In some other embodiments the CAM is divided into more than two sections, and a result or action is associated with each section.
In another aspect of the invention, in a network packet router, an ingress port is provided, comprising an interface for receiving packets, a first mechanism for noting header combinations and values, and egress ports for transmission, for individual ones of the received packets, and a second mechanism comparing the headers and values with a rule set comprising header combinations and values and egress ports, and returning a rule for the packet.
In some embodiments the rule returned is a pass or drop determination for the packet. Also in some embodiments the rule set association is in the form of a lookup table. Further the network may be the Internet. In some embodiments there may be a second rule set association for accomplishing ingress rule determinations without egress port numbers. Also in some embodiments a content addressable memory (CAM) is used for header combination matches, and an associated rule is determined by the address location of any match. The CAM may be divided into two sections, and a pass or drop determination is determined by the section wherein the address lies for the content match. In some embodiments the CAM is divided into more than two sections, and a result or action is associated with each section.
In yet another aspect a network packet router is provided, comprising one or more ingress ports, and one or more egress ports. The router is characterized in that individual ones of the ingress ports comprise a first mechanism for noting header field combinations and values, and egress ports for transmission, for individual ones of the received packets, and a second mechanism comparing the headers with rules associated with the egress ports and field values, and returning a rule determination for the packet.
In some embodiments of the router the rule returned determines pass or drop for the associated packet, and in some embodiments the rule set association takes the form of a lookup table. The network may be the Internet. In some cases there may be a second rule set association for accomplishing ingress pass/drop determinations without egress port numbers. Also in some cases a content addressable memory (CAM) is used for header combination matches, and a rule is determined by the address location of any match. The CAM may be divided into two sections, and a pass or drop determination is determined by the section wherein the address lies for the content match. Further, in some cases the CAM is divided into more than two sections, and a result or action is associated with each section.
In yet another aspect of the invention, in a network packet router having one or more ingress and egress ports, a method implemented at an ingress port for determining both ingress and egress rules for packets is provided, comprising the steps of (a) noting header combinations and values, and egress port destination for incoming packets; (b) comparing the header combinations and values and egress port destinations with a rule set associated with the header combinations and values including egress port destinations; and (c) returning a rule for the packet.
In preferred embodiments, in step (c), the rule returned indicates pass or drop for the associated packet. Also, in some preferred embodiments the rule set associations take the form of a lookup table. The network may be the Internet.
In some embodiments of the method there is a second lookup in a separate rule set association for accomplishing ingress rule application determinations without egress port numbers.
In some embodiments a content addressable memory (CAM) is consulted for rule set matches, and a rule is determined by the address location of any match. The CAM may be divided into two sections, and pass or drop is then determined by the section wherein the address is found for a content match. In some cases the CAM is divided into more than two sections, and each section is associated with a different result or action.
In embodiments of the invention described in enabling detail below, for the first time a system and method is provided wherein egress port pass/drop determinations may be made at ingress.